HJ41 称砝码

本节目标：理解“HJ41 称砝码”的核心思路，并能把它用于实际开发或面试表达。

说明：原 OneNote 中有图片引用，但图片未包含在导出目录中；本页保留了可用的文字与代码内容。 中等 通过率：32.70% 时间限制：1秒 空间限制：32M 知识点==字符串====哈希== 描述 现有n种砝码，重量互不相等，分别为 m1,m2,m3…mn ； 每种砝码对应的数量为 x1,x2,x3...xn 。现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量。

注： 称重重量包括 0 数据范围：每组输入数据满足

输入描述： 对于每组测试数据： 第一行：n --- 砝码的种数(范围[1,10]) 第二行：m1 m2 m3 ... mn --- 每种砝码的重量(范围[1,2000]) 第三行：x1 x2 x3 .... xn --- 每种砝码对应的数量(范围[1,10]) 输出描述： 利用给定的砝码可以称出的不同的重量数 示例1 输入： 21 22 1 ==复制== 输出： 5 ==复制== 说明： 可以表示出0，1，2，3，4五种重量。

这个问题可以通过动态规划的方法来解决，类似于处理“多重背包问题”。基本思路是维护一个能够称出的重量集合，并逐步通过当前砝码的不同数量来扩展这个集合。

算法描述：

1. 初始化: 创建一个布尔数组 dp，其中 dp[j] 表示重量 j 是否可以被称出。初始化 dp[0] = True 表示重量 0 总是可以称出。

2. 遍历砝码：对于每种砝码，考虑每一个可能使用的数量，从最大总重量递减到当前砝码重量，更新能够称出的重量集合。

3. 统计结果：最终，遍历 dp 数组，统计为 True 的项的数量，即为能称出的不同重量的总数。

def count_possible_weights(n, weights, counts):

计算所有砝码的最大可能总重量

max_weight = sum(weights[i] * counts[i] for i in range(n))

创建dp数组，初始化重量0为可达

dp = [False] * (max_weight + 1) dp[0] = True

遍历每种砝码

for i in range(n): weight = weights[i] count = counts[i]

从最大重量向下遍历到0，更新dp数组

for j in range(max_weight, weight - 1, -1): for k in range(1, count + 1): if j >= k * weight and dp[j - k * weight]: dp[j] = True

计算可以称出的不同重量的数量

return sum(dp)

读取输入信息

n = int(input().strip()) # 砝码种数 weights = list(map(int, input().strip().split())) # 每种砝码的重量 counts = list(map(int, input().strip().split())) # 每种砝码的数量

计算结果

result = count_possible_weights(n, weights, counts)

输出结果

print(result)

示例解释：

对于输入样例：

2
1 2
2 1

初始化时，dp[0] = True。考虑第一种砝码（重量为1，数量为2），可以更新称重为1和2的可能性。接着，考虑第二种砝码（重量为2，数量为1），可以进一步更新称重为2、3和4的可能性。最终，dp[1]、dp[2]、dp[3] 和 dp[4] 都会被标记为 True，因此可以称出的重量有0, 1, 2, 3, 4，共计5种不同的重量。

这个方法利用动态规划逐步构建了可能的重量组合，有效地解决了问题。

dp = [False] * (max_weight + 1) 在动态规划中，我们经常需要创建一个数组或列表来保存每一种状态的可能性，从 0 到 max_weight 的每一个重量值都需要被考虑。这里的 max_weight 是通过砝码的最大可能组合重量来计算的，即所有砝码的总重量。

为什么要 max_weight + 1？

1. 索引从零开始：在 Python 中，列表的索引是从 0 开始的。如果我们创建一个长度为 max_weight 的列表，那么它的索引范围将是 0 到 max_weight - 1。这样，我们无法直接访问到 max_weight 这个重量值，因为尝试访问 dp[max_weight] 将会引发索引错误（IndexError）。

2. 包含边界：为了能够方便地处理从 0 到 max_weight 的所有可能重量（包括 0 和 max_weight 自身），我们需要创建一个长度为 max_weight + 1 的列表。这样做确保了 dp[max_weight] 是一个有效的索引，我们可以在不出错的情况下检查或设置重量 max_weight 是否可能。

具体示例：

假设所有砝码的总重量 max_weight 是 10，我们想要处理的重量范围是从 0 到 10（包括 0 和 10）。因此，我们需要 11 个位置来存储这些信息（从 0 到 10 共 11 个数）。如果我们创建了一个长度为 10 的列表，它的索引将只能从 0 到 9，这样我们就无法存储信息关于重量 10 的可能性。

总结来说，使用 max_weight + 1 作为列表长度是为了确保所有的重量值（包括 0 和 max_weight）都能够被我们的程序正确处理和存储，从而避免索引越界错误，并完整地覆盖所有需要考虑的情况。这是在处理基于数组或列表的动态规划问题时一个常见的技巧。